package Hot100.Medium.BinarySearch;

public class LC300 {
    public static void main(String[] args) {

    }

    public int lengthOfLIS(int[] nums){
        int[] tails = new int[nums.length];
        int n = nums.length;
        int size = 0;
        for(int num : nums){
            // 二分查找每一个num在tails应该放的位置，如果num比tail中最后一个数小，就会将其替换，因为无法满足递增
            // 如果比tail最后一个数还大，证明需要将其加入到tail的最后。
            int left = 0, right = size - 1;
            while(left <= right){
                int mid = left + (right - left) / 2;
                if(tails[mid] >= num){
                    right = mid - 1;// 缩小右边界，往左找第一个>=num的位置
                } else {
                    left = mid + 1; // tails[mid] < num，往右边找
                }
            }
            tails[left] = num;
            if (left == size) {
                size++;
            }
        }
        return size;
    }
}
